// 84.[单调栈] 柱状图中最大的矩形
// https://leetcode.cn/problems/largest-rectangle-in-histogram/
//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为
// 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 示例 1: 输入：heights =
//[2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10 示例 2：
//输入： heights = [2,4]
//输出： 4
//提示：1 <= heights.length <=105,0 <= heights[i] <= 104
#include <bits/stdc++.h>
using namespace std;
#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

class Solution {
 public:
  // 找到左右两侧最近高度小于h的柱子，这两根柱子之间(不含本身)
  int largestRectangleArea(vector<size_t>& heights) {
    size_t ans = 0;
    vector<size_t> stk;                  // index stack
    heights.insert(heights.begin(), 0);  //首尾哨兵
    heights.push_back(0);
    for (size_t iRight = 0; iRight < heights.size(); iRight++) {
      while (!stk.empty() && heights[stk.back()] > heights[iRight]) {
        size_t cur = stk.back();
        stk.pop_back();
        size_t left = stk.back();
        ans = std::max(ans, (iRight - left - 1) * heights[cur]);  // (L,R)
      }
      stk.push_back(iRight);
    }
    return (int)ans;
  }
};
int main() {
  vector<size_t> heights = {2, 1, 5, 6, 2, 3};
  for (auto n : heights) PF("%d,", n);
  PF("\n");
  Solution sol;
  sol.largestRectangleArea(heights);
  return 0;
}
